#include "stdafx.h"
#include "Comparable.h"
#pragma once; 

template <class T> class Array;

template <class T> 
class Sort           
{
public:
	virtual void sort(Array<T>&  myArray, Comparable<T>* cp) = 0;
};


// Insertion sort
template <class T> 
class InsertionSort: public Sort<T>
{
private:
	static InsertionSort<T>* insertSort;
	static int countIS;
	InsertionSort()
	{
	}
	~InsertionSort()
	{
	}
public:

	static InsertionSort* getSortObject()
	{
		if (insertSort == NULL)
			insertSort = new InsertionSort<T>();
		countIS++;
		return insertSort;
	}
	static void releaseSortObject()
	{
		if( --countIS == 0)
			delete insertSort;
	}

	void sort(Array<T>&  myArray, Comparable<T>* cp) 
	{
		int i, j;
		T index;
		for(i=1; i < myArray.getSize();i++)
		{
			index  = myArray[i];
			j = i;
			while((j > 0) && (cp->compare(myArray[j-1] ,index))==TRUE)
			   {
				myArray[j] = myArray[j-1];
				j = j-1;
			   }
		   myArray[j] = index;
		}

	}
};

template <class T> InsertionSort<T>* InsertionSort<T>::insertSort = NULL;
template <class T> int InsertionSort<T>::countIS = 0;

// Shell sort
template <class T> 
class ShellSort: public Sort<T>
{
private:
	static ShellSort<T>* shellSort;
	static int countSS;
	ShellSort()
	{
	}
	~ShellSort()
	{
	}
public:

	static ShellSort* getSortObject()
	{
		if (shellSort == NULL)
			shellSort = new ShellSort();

		countSS++;
		return shellSort;
	}
	static void releaseSortObject()
	{
		if( --countIS == 0)
			delete shellSort;
	}
	void sort(Array<T>&  myArray, Comparable<T>* cp)
	{
		int j,i,k,m, n = myArray.getSize();
		T mid;
		for(m = n/2;m>0;m/=2)
		{
			for(j = m;j< n;j++)
			{
				for(i=j-m;i>=0;i-=m)
				{
					if((cp->compare()(myArray[i+m] ,myArray[i]))==TRUE)
						break;
					else
					{
						mid = myArray[i];
						myArray[i] = myArray[i+m];
						myArray[i+m] = mid;
					}
				}
			}
		}
	}
};
template <class T> ShellSort<T>* ShellSort<T>::shellSort = NULL;
template <class T> int ShellSort<T>::countSS =0;